#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


int longestPalindromeSubseq(string s) {
    //
    vector<vector<int> > dp(s.size(), vector<int>(s.size(), 0));
    //dp 代表 i j 字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
    // dp[i][j]=dp[i+1][j-1]+2;  类似与一个数组一个前移一个后移 如果相同就+2


    // 行应该由下面向上走 因为是i+1确定的i 列应该从左边向右边走

    //初始化 对于距离为0的 应该初始化为1 因为一个字符肯定是

    for (int i = 0; i < s.size(); ++i) {
        dp[i][i] = 1;
    }


    for (int i = s.size() - 1; i >= 0; --i) {
        // j肯定要比i大才行 因为求的事他俩距离
        for (int j = i + 1; j < s.size(); ++j) {

            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }

        }

    }

    return dp[0][s.size() - 1];


}